# 二分法查找O(logn)
# def binary_search(l,num):
#     first = 0  # 构造初始下标
#     last = len(l)-1  # 构造最后一个元素下标
#     while first <= last:  # 可能找到的范围
#         mid = (last - first)//2  # 构造中间值下标
#         if l[mid] == num:
#             return True
#         elif l[mid] > num:
#             last = mid - 1
#         else:
#             first = mid + 1
#     else: # 找不到情况
#         return False
#
# if __name__ == '__main__':
#     li = [1,2,3,4,5,8,23,34,56,67,77,676,888,999,12121]
#     print(binary_search(li,34))


# 二分查找递归
# def binary_search(l,num):
#     if l == []:
#         return False
#     else:
#         mid = len(l)//2
#         if l[mid] == num:
#             return True
#         elif l[mid] > num:
#             return binary_search(l[:mid],num)
#         else:
#             return binary_search(l[mid+1:],num)
#
# if __name__ == '__main__':
#     li = [1,2,3,4,5,6]
#     print(binary_search(li,4))